// 给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。

// 两棵树重复是指它们具有相同的结构以及相同的结点值。

// 示例 1：

//         1
//        / \
//       2   3
//      /   / \
//     4   2   4
//        /
//       4
// 下面是两个重复的子树：

//       2
//      /
//     4
// 和

//     4
// 因此，你需要以列表的形式返回上述重复子树的根结点。



/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode[]}
 */
var findDuplicateSubtrees = function (root) {
  let memo = {};
  let traverse = (root) => {
      if (!root) return '#';
      let leftStr = traverse(root.left);
      let rightStr = traverse(root.right);
      // 后序遍历，获得某一结点的子树结构（序列化的字符串）
      let rootStr = `${leftStr},${rightStr},${root.val}`;
      // 通过比较字符串知道是否结构相同
      if (!memo[rootStr]) {
          memo[rootStr] = {num: 1, result: root};
      } else {
          memo[rootStr].num ++;
      }
      return rootStr;
  }
  traverse(root);
  let res = [];
  [...Object.keys(memo)].forEach(item => {
      if(memo[item].num > 1) {
          res.push(memo[item].result)
      }
  })
  return res;
};
